package com.tys.algorithm.advanced.test.class03;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 使用循环数组实现队列
 */
public class Code04_ArrayToQueue {

    public static class MyQueue {
        private int[] arr;
        private int pushi;
        private int polli;
        private int size;
        private final int limit;

        public MyQueue(int limit) {
            arr = new int[limit];
            pushi = 0;
            polli = 0;
            size = 0;
            this.limit = limit;
        }

        public void push(int value) {
            if (size == limit) {
                throw new RuntimeException("full");
            }
            size++;
            arr[pushi] = value;
            pushi = nextIndex(pushi);
        }

        public int pop() {
            if (size == 0) {
                throw new RuntimeException("empty");
            }
            size--;
            int ans = arr[polli];
            polli = nextIndex(polli);
            return ans;
        }

        public boolean isEmpty() {
            return size == 0;
        }

        private int nextIndex(int i) {
            return i < limit - 1 ? i + 1 : 0;
        }

    }

    public static boolean isEqual(Integer o1, Integer o2) {
        if (o1 == null && o2 != null) {
            return false;
        }
        if (o1 != null && o2 == null) {
            return false;
        }
        if (o1 == null && o2 == null) {
            return true;
        }

        boolean flag = o1.equals(o2);
        if (!flag) {
            System.out.println("o1: " + o1 + ",o2: " + o2);
        }
        return flag;
    }

    public static void main(String[] args) {
        int oneTestDataNum = 100;
        int value = 10000;
        int testTimes = 100000;
        System.out.println("begin");

        for (int i = 0; i < testTimes; i++) {
//            System.out.println("i:" + i);

            int limit = (int) (Math.random() * value);
            MyQueue myQueue = new MyQueue(limit);
            Queue<Integer> queue = new LinkedList<>();
            for (int j = 0; j < oneTestDataNum; j++) {
                int numq = (int) (Math.random() * value);
                if (queue.isEmpty()) {
                    myQueue.push(numq);
                    queue.offer(numq);
                } else {
                    if (Math.random() < 0.5) {
                        myQueue.push(numq);
                        queue.offer(numq);
                    } else {
                        if (!isEqual(myQueue.pop(), queue.poll())) {
                            System.out.println("limit:" + myQueue.limit);
                            System.out.println("size:" + myQueue.size);
                            System.out.println("Oops2!");
                            return;
                        }
                    }
                }
            }
        }
        System.out.println("finish!");

    }
}
